package com.leetcode.array;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2019/9/18
 * @description:	[27]
 * 移除元素
 * 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
 *
 * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
 *
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RemoveElement27 {

	/**
	 * -- 原地算法，O(1) 额外空间
	 * 将相同的移到右边，并与右边的进行比较
	 * @改变了原有顺序版本
	 * @param nums
	 * @param val
	 * @return
	 */
	public static int removeElement(int[] nums, int val) {
		///边界条件判断
		if (nums == null || nums.length == 0){
			return 0;
		}

		///1.统计有效元素的个数	///其实 swap 参数都不需要设置
		int ans=0,right=nums.length-1,
				swap=0;

		for (int i = 0; i <= right; i++) {
			//如果相同，交换到最后
			if (nums[i]==val){
//				swap = nums[i];
//				nums[i]=nums[right];
//				nums[right--]=swap;
//				ans++;
				nums[i--]=nums[right];
				nums[right--]=val;
			}
			//不相同，
			else {
				ans++;
			}
		}

		return ans;
	}

	/**
	 *
	 * @param nums
	 * @param val
	 * @return
	 */
	public static int removeElement2(int[] nums, int val) {
		if (nums == null || nums.length == 0){
			return 0;
		}
		int j = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != val) {
				nums[j] = nums[i];
				j++;
			}
		}
		return j;
	}

	public static void main(String[] args) {
		int[] ints = {0, 1, 2, 2, 3, 0, 4, 2};
		///ints = new int[]{3, 2, 2, 3};
		int val=3;
		val =2;
		removeElement2(ints,val);
		System.out.println(Arrays.toString(ints));
	}

}
